package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_105_从前序与中序遍历序列构造二叉树 {
    @Test
    public void main() {

        System.out.println(buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7}));
    }

    /**
    题目：给定两个整数数组 preorder 和 inorder ，
         其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

     示例 1:
     输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     输出: [3,9,20,null,null,15,7]

     示例 2:
     输入: preorder = [-1], inorder = [-1]
     输出: [-1]

    分析：【P 💜💜💜】
       1.递归：根据前序遍历preorder的首节点，即为根节点。
               在中序遍历inorder中找到 == preorder[首节点] 的下标 topPoint，topPoint下标左边为left,右边为right
               递归下去：单步操作、终止条件、返回值
             --优化：Map存储节点在inoder中的位置，不用每次for循环
             --执行用时：3 ms, 在所有 Java 提交中击败了53.62%的用户
             --时长：超过30分钟

    边界值 & 注意点：
       1.
     **/
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    //递归三部曲：单步操作、终止条件、返回值
    private TreeNode dfs(int[] preoder, int[] inoder, int pStart, int pEnd, int iStart, int iEnd) {
        if(pStart>pEnd) return  null;
        TreeNode point = new TreeNode(preoder[pStart]);
        if(pStart==pEnd) return  point;
        //找出父节点在 iStart 、 iEnd 中的位置
        int  parentIndex;
        for (parentIndex = iStart; parentIndex <= iEnd; parentIndex++) {
            if (preoder[pStart] ==  inoder[parentIndex])
                break;
        }
        int numb = parentIndex - iStart; //左节点，节点数
        point.left=dfs(preoder,inoder,pStart+1,pStart+numb,iStart,parentIndex-1);//左树
        point.right=dfs(preoder,inoder,pStart+numb+1,pEnd,parentIndex+1,iEnd);//右树
        return point;
    }
}
